package com.lw.leetcode.str.b;

/**
 * Created with IntelliJ IDEA.
 * 2182. 构造限制重复的字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/20 22:40
 */
public class RepeatLimitedString {

    public static void main(String[] args) {
        RepeatLimitedString test = new RepeatLimitedString();

        // "zzcccac"
//        String str = "cczazcc";
//        int k = 3;

        // "zzcccac"
//        String str = "cczzazcc";
//        int k = 3;

        // "bbabaa"
        String str = "aababab";
        int k = 2;

        String string = test.repeatLimitedString(str, k);
        System.out.println(string);
    }

    public String repeatLimitedString(String s, int repeatLimit) {
        int length = s.length();
        char[] items = s.toCharArray();
        int[] arr = new int[26];
        for (int i = 0; i < length; i++) {
            arr[items[i] - 'a']++;
        }
        int index = 0;
        for (int j = 25; j >= 0; j--) {
            if (arr[j] == 0) {
                continue;
            }
            if (arr[j] >= repeatLimit) {
                if (index != 0 && items[index - 1] - 'a' == j) {
                    arr[j] -= repeatLimit - 1;
                    for (int k = repeatLimit - 1; k > 0; k--) {
                        items[index++] =  (char) (j + 'a');
                    }
                } else {
                    arr[j] -= repeatLimit;
                    for (int k = repeatLimit; k > 0; k--) {
                        items[index++] =  (char) (j + 'a');
                    }
                }
                boolean f = false;
                for (int k = j - 1; k >= 0; k--) {
                    if (arr[k] != 0) {
                        arr[k]--;
                        items[index++] = (char) (k + 'a');
                        f = true;
                        break;
                    }
                }
                if (!f) {
                    return String.valueOf(items, 0, index);
                }
                j++;
            } else {
                for (int k = arr[j]; k > 0; k--) {
                    items[index++] =  (char) (j + 'a');
                }
                arr[j] = 0;
            }
        }
        return String.valueOf(items, 0, index);
    }

}
